

//
//  LinkedList_sort.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/9.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension LinkedList where Element: Comparable {
    
    /// 排序
    public func sort() {
        if _size < 2 { return }
        #if true
        _quickSort(first, last)
        #else
        _mergeSort(first!, _size)
        #endif
        
        #if false
        _insertionSort(first, last)
        #endif
    }
    
    /// 合并
    public func merge(_ other: LinkedList<Element>) {
        if _size < 2 { return }
        _mergeSort(first!, _size)
    }
}

extension LinkedList where Element: Comparable {

    // 对起始为p的n个元素排序
    func _mergeSort(_ p: LinkedListNode<Element>, _ n: Int) {
        if n < 2 { return }
        let mid = n / 2
        var midNode = p
        for _ in 0..<mid { midNode = p.successor! }
        _mergeSort(p, mid)
        _mergeSort(midNode, n - mid)
        _merge(p, mid, self, midNode, n - mid)
    }
    
    /// 合并当前链表从p开始的n个节点和另一个链表从q开始的m个节点
    func _merge(_ p: LinkedListNode<Element>, _ n: Int, _ other: LinkedList<Element>, _ q: LinkedListNode<Element>, _ m: Int) {
        
        // this is too expensive
        let copyList = LinkedList<Element>()
        var begin = p
        for _ in 0..<n {
            copyList.insertAsLast(begin.value!)
            begin = begin.successor!
        }
        
        var fbegin = p
        var sbegin = q
        var cbegin = copyList.first
        var i = 0, j = 0, k = 0
        while j < n || k < m {
            
            if (j < n) && (k >= m || cbegin! <= sbegin ) {
                fbegin.value = cbegin?.value
                fbegin = fbegin.successor!
                cbegin = cbegin?.successor!
                i += 1
                j += 1
            }
            
            if (k < m) && (j >= n || sbegin < cbegin! ) {
                fbegin.value = sbegin.value
                fbegin = fbegin.successor!
                sbegin = sbegin.successor!
                i += 1
                k += 1
            }
        }
    }
    
    func _quickSort(_ p: LinkedListNode<Element>?, _ q: LinkedListNode<Element>?) {
        if p === q { return }
        guard let p = p, let q = q else { return }
        let pivot = _partition(p, q)
        if pivot !== p { // 避免越界
            _quickSort(p, pivot.predecessor)
        }
        if pivot !== q { // 避免越界
            _quickSort(pivot.successor, q)
        }
    }
    
    func _partition(_ p: LinkedListNode<Element>, _ q: LinkedListNode<Element>) -> LinkedListNode<Element> {
        let pivot = q
        var end = p
        var node = p // 1 2
        while node !== q {
            if node <= pivot {
                (end.value, node.value) = (node.value, end.value)
                end = end.successor! // its safe
            }
            
            node = node.successor! // its safe
        }
        
        (end.value, pivot.value) = (pivot.value, end.value)
        return end
    }
    
    func _insertionSort(_ p: LinkedListNode<Element>?, _ q: LinkedListNode<Element>?) {
        if p === q { return }
        guard let p = p, let q = q else { return }
        var i = p.successor

        while i !== q.successor {
            var j = p
            while j !== i?.successor {
                if j > i! { // also safe
                    (j.value, i!.value) = (i!.value, j.value)
                }
                j = j.successor!
            }
            i = i?.successor
        }
    }
}
